package MiddlePractice;

import java.util.LinkedHashMap;

public class Demo208 {
//	208. 实现 Trie (前缀树)
//	Trie（发音类似 "try"）或者说 前缀树 是一种树形数据结构，用于高效地存储和检索字符串数据集中的键。
//	这一数据结构有相当多的应用情景，例如自动补完和拼写检查。
//
//	请你实现 Trie 类：
//
//	Trie() 初始化前缀树对象。
//	void insert(String word) 向前缀树中插入字符串 word 。
//	boolean search(String word) 如果字符串 word 在前缀树中，返回 true（即，在检索之前已经插入）；否则，返回 false 。
//	boolean startsWith(String prefix) 如果之前已经插入的字符串 word 的前缀之一为 prefix ，返回 true ；否则，返回 false 。

	public class Trie {
		
		private char val;
		private LinkedHashMap<Character, Trie> children;
		private boolean isEnd;
		
		public Trie() {
			val = '#';
			children = new LinkedHashMap<>();
			isEnd = false;
		}
		
		public Trie(char ch) {
			val = ch;
			children = new LinkedHashMap<>();
			isEnd = false;
		}
		
		public void insert(String word) {
			Trie node = this;
			
			for(int i=0; i<word.length(); i++) {
				char ch = word.charAt(i);
				
				if(!node.children.containsKey(ch)) {
					Trie child = new Trie(ch);
					node.children.put(ch, child);
				}
				
				node = node.children.get(ch);
			}
			node.isEnd = true;
		}
		
		public Trie searchPrefix(String prefix) {
			Trie node = this;
			
			for(int i=0; i<prefix.length(); i++) {
				char ch = prefix.charAt(i);
				
				if(!node.children.containsKey(ch)) {
					return null;
				}
				
				node = node.children.get(ch);
			}
			
			return node;
		}
		
		public boolean search(String word) {
			//找到以word为前缀的路径  并且这个路径没有往下走的路径了  （叶子节点结尾）
			Trie node = searchPrefix(word);
			return node != null && node.isEnd;
		}
		
		public boolean startsWith(String prefix) {
			return searchPrefix(prefix) != null;
		}
		
	}
	
}
